class Solution(object):
    def maxSumOfThreeSubarrays(self, nums, k):
        n = len(nums)
        pre = nums.copy()
        for i in range(1, n):
            pre[i] += pre[i - 1]
        DP = [[0, 0] for _ in range(n)]
        DP[k - 1] = [pre[k - 1], 0]
        for i in range(k, n):
            if pre[i] - pre[i - k] > DP[i - 1][0]:
                DP[i] = [pre[i] - pre[i - k], i - k + 1]
            else:
                DP[i] = [DP[i - 1][0], DP[i - 1][1]]
        DP2 = [[0, 0, 0] for _ in range(n)]
        DP2[2 * k - 1] = [pre[2 * k - 1], 0, k]
        for i in range(2 * k, n):
            now_val = pre[i] - pre[i - k]
            if now_val + DP[i - k][0] > DP2[i - 1][0]:
                DP2[i] = [now_val + DP[i - k][0], DP[i - k][1], i - k + 1]
            else:
                DP2[i] = [DP2[i - 1][0], DP2[i - 1][1], DP2[i - 1][2]]
        DP3 = [[0, 0, 0, 0] for _ in range(n)]
        DP3[3 * k - 1] = [pre[3 * k - 1], 0, k, 2 * k]
        for i in range(3 * k, n):
            now_val = pre[i] - pre[i - k]
            if now_val + DP2[i - k][0] > DP3[i - 1][0]:
                DP3[i] = [now_val + DP2[i - k][0], DP2[i - k][1], DP2[i - k][2], i - k + 1]
            else:
                DP3[i] = [DP3[i - 1][0], DP3[i - 1][1], DP3[i - 1][2], DP3[i - 1][3]]
        return [DP3[-1][1], DP3[-1][2], DP3[-1][3]]

data = Solution()
nums = [1, 2, 1, 2, 6, 7, 5, 1]
k = 2
print(data.maxSumOfThreeSubarrays(nums, k))
